package leetCode.offer37;

import java.util.*;

/**
 * 请实现两个函数，分别用来序列化和反序列化二叉树。
 * 你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，
 * 你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
 *
 * 提示：输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
 */
public class Codec1 implements Codec{


    /**
     * 层次遍历解法，超出内存限制
     * @param root
     * @return
     */
    @Override
    public String serialize(TreeNode root) {
        if(root==null) return null;
        if(root.right==null&&root.left==null) return root.val+"";
        List<List<Integer>> array = levelOrder(root);
        StringBuilder result = new StringBuilder();
        for(List<Integer> list:array){
            for (Integer item:list){
                result.append(item).append("|");
            }
            result.replace(result.length()-1,result.length(),"&");
        }
        result.replace(result.length()-1,result.length(),"");
        return result.toString();
    }

    @Override
    public TreeNode deserialize(String data) {
        if(data==null) return null;
        if(!data.contains("&")) new TreeNode(Integer.parseInt(data));
        String[] level = data.split("&");
        List<List<TreeNode>> array = new ArrayList<>();
        for(String str:level) {
            List<TreeNode> item = new ArrayList<>();
            String[] nums = str.split("\\|");
            for(String num:nums){
                if(num.equals("null")){
                    item.add(null);
                }else item.add(new TreeNode(Integer.parseInt(num)));
            }
            array.add(item);
        }
       for(int i=0;i<array.size()-1;i++){
           List<TreeNode> first = array.get(i);
           List<TreeNode> second = array.get(i+1);
           for(int j=0;j<first.size();j++){
               if(first.get(j)!=null){
                   first.get(j).left = second.get(j*2);
                   first.get(j).right = second.get(j*2+1);
               }else{
                   second.add(j*2,null);
                   second.add(j*2+1,null);
               }
           }
       }
        return array.get(0).get(0);
    }

    /**
     * 将层次遍历的结果存入二维数组中
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue= new LinkedList<>();
        List<List<Integer>> result = new ArrayList<>();
        if(root!=null) queue.add(root);
        while(!queue.isEmpty()){
            List<Integer> temp = new ArrayList<>();
            int size = queue.size();
            for(int i=0;i<size;i++) {
                TreeNode node = queue.poll();
                if(node==null){
                    temp.add(null);
                }
                else {
                    temp.add(node.val);
                    queue.add(node.left);
                    queue.add(node.right);
                }
            }
            for(Integer n:temp){
                if(n!=null){
                    result.add(temp);
                    break;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Codec codec = new Codec1();
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(5);
        System.out.println(codec.serialize(root));
        TreeNode node = codec.deserialize(codec.serialize(root));
        System.out.println("完成！！");

    }
}
